package 八大排序;

/**
 * 堆排序：对简单选择排序的优化。
 *                 a[0]
 *                /    \
 *              /       \
 *            a[1]      a[2]
 *            /  \       /  \
 *          /     \    /     \
 *         a[3] a[4] a[5]   a[6]
 *         ...
 * @author 刘学松
 * @date 2021/2/25 17:41
 */
public class 堆排序 {
    public static void main(String[] args) {
        ArrayUtils.printArray(heapSort(ArrayUtils.array));
    }

    public static int[] heapSort(int[] a) {
        // 初始化堆，堆顶元素为最大值
        buildHeap(a);
        // 从最后一个元素(节点)开始遍历
        for (int i = a.length-1; i >= 0; i--) {
            // 最后一个元素和堆顶元素进行交换，此时最后一个元素变成最大值
            swap(a, i, 0);
            // 继续从堆顶开始堆化
            heapify(a, i, 0);
        }
        return a;
    }

    /**
     * 初始化构造一个堆
     * @param a 数组
     */
    public static void buildHeap(int[] a) {
        // 最后一个元素下标
        int last = a.length - 1;
        // 通过最后一个元素取到最后一个父节点下标
        int parent = (last - 1) / 2;
        // 最后一个父节点下标往前都会是父节点
        for (int i = parent; i >= 0; i--) {
            heapify(a, a.length, i);
        }
    }

    /**
     * 从第i个元素进行堆化操作
     * @param a 数组
     * @param length 需要堆化的长度
     * @param i 第几个元素开始
     */
    public static void heapify(int[] a, int length, int i) {
        // 递归结束出口
        if (i >= length) {
            return;
        }
        // c1为第i个元素下的左边子节点下标，c2为右边子节点下标
        int c1 = i * 2 + 1;
        int c2 = i * 2 + 2;
        // 记录最大数的下标
        int max = i;
        if (c1 < length && a[c1] > a[max]) {
            max = c1;
        }
        if (c2 < length && a[c2] > a[max]) {
            max = c2;
        }
        if (max != i) {
            swap(a, i, max);
            // 交换后会有一个子节点变小，继续对该子节点进行堆化操作
            heapify(a, length, max);
        }
    }

    /**
     * 数组元素交换
     * @param a 数组
     * @param i 第i个元素
     * @param j 第j个元素
     */
    public static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
